- Title
- Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation
- Creator
- Wirth, Fabian R.; Stüdl, Sonja; Yu, Jia Yuan; Corless, Martin; Shorten, Robert
- Relation
- Journal of the ACM Vol. 66, Issue 4, no. 24
- Publisher Link
- http://dx.doi.org/10.1145/3312741
- Publisher
- Association for Computing Machinery
- Resource Type
- journal article
- Date
- 2019
- Description
- A stochastic algorithm is presented for a class of optimisation problems that arise when a group of agents compete to share a single constrained resource in an optimal manner. The approach uses intermittent single-bit feedback, which indicates a constraint violation and does not require inter-agent communication. The algorithm is based on a positive matrix model of AIMD, which is extended to the nonhomogeneous Markovian case. The key feature is the assignment of back-off probabilities to the individual agents as a function of the past average access to the resource. This leads to a nonhomogeneous Markov chain in an extended state space, and we show almost sure convergence of the average access to the social optimum.
- Subject
- nonhomogeneous place-dependent Markov chains; AIMD; invariant measure; iterated function systems; almost sure convergence; optimisation
- Identifier
- http://hdl.handle.net/1959.13/1463104
- Identifier
- uon:46639
- Identifier
- ISSN:0004-5411
- Language
- eng
- Reviewed
- Hits: 1363
- Visitors: 1354
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|